package recursion.leetcode.editor.cn;


import recursion.leetcode.editor.cn.common.TreeNode;

public class PathSum{
      public static void main(String[] args) {
           Solution solution = new PathSum().new Solution();
           TreeNode treeNode1 = new TreeNode(5);
           TreeNode treeNode2 = new TreeNode(4);
           TreeNode treeNode3 = new TreeNode(11);
           TreeNode treeNode4 = new TreeNode(2);
           TreeNode treeNode5 = new TreeNode(5);
           treeNode1.left = treeNode2;
           treeNode2.left = treeNode3;
           treeNode3.right = treeNode4;
           treeNode3.left = treeNode5;
            System.out.println(solution.hasPathSum(treeNode1,22));
      }
      //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int sum = 0;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        if(root.left == null  && root.right == null && sum + root.val== targetSum){
            return true;
        }
        sum = sum+root.val;
        return hasPathSum(root.left,targetSum)||hasPathSum(root.right,targetSum);
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}